package geometry;

import java.util.Arrays;

public class Geometry {

	static class Point {
		double x, y;
	}

	static class Segment {
		Point p1, p2;
	}

	static final double eps = 1e-9;

	/** object */

	static boolean segmentIntersect(Segment s1, Segment s2) {
		double d1, d2, d3, d4;
		d1 = cross_product(s1.p1, s2.p1, s2.p2);
		d2 = cross_product(s1.p2, s2.p1, s2.p2);
		d3 = cross_product(s2.p1, s1.p1, s1.p2);
		d4 = cross_product(s2.p2, s1.p1, s1.p2);
		if (((d1 > eps && d2 < -eps) || (d1 < -eps && d2 > eps))
				&& ((d3 > eps && d4 < -eps) || (d3 < -eps && d4 > eps)))
			return true;
		else if (equal(d1, 0) && onSegment(s1.p1, s2.p1, s2.p2))
			return true;
		else if (equal(d2, 0) && onSegment(s1.p2, s2.p1, s2.p2))
			return true;
		else if (equal(d3, 0) && onSegment(s2.p1, s1.p1, s1.p2))
			return true;
		else if (equal(d4, 0) && onSegment(s2.p2, s1.p1, s1.p2))
			return true;
		return false;
	}

	/** private */
	private static boolean onSegment(Point p1, Point p2, Point p3) {
		if (p1.x + eps > min(p2.x, p3.x) && p1.x - eps < max(p2.x, p3.x)
				&& p1.y + eps > min(p2.y, p3.y) && p1.y - eps < max(p2.y, p3.y))
			return true;
		return false;
	}

	static boolean onSegment(Point p, Segment s) {
		double d = cross_product(p, s.p1, s.p2);
		if (!equal(d, 0.0))
			return false;
		else if (p.x + eps > min(s.p1.x, s.p2.x)
				&& p.x - eps < max(s.p1.x, s.p2.x)
				&& p.y + eps > min(s.p1.y, s.p2.y)
				&& p.y - eps < max(s.p1.y, s.p2.y))
			return true;
		return false;
	}

	static double area(Point p1, Point p2, Point p3) {
		return abs(cross_product(p1, p2, p3)) / 2.0;
	}

	/**
	 * @param p1
	 *            source
	 * @param p2
	 *            destination
	 * @param p3
	 *            destination
	 * @return cross product of ( p1->p2 , p1->p3 )
	 */
	static double cross_product(Point p1, Point p2, Point p3) {
		return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
	}

	static double distance(Point p1, Point p2) {
		return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y)
				* (p1.y - p2.y));
	}

	/** raw data */

	static double area(double x1, double y1, double x2, double y2, double x3,
			double y3) {
		return abs(cross_product(x2 - x1, y2 - y1, x3 - x1, y3 - y1)) / 2.0;
	}

	static double cross_product(double x1, double y1, double x2, double y2) {
		return x1 * y2 - x2 * y1;
	}

	static double distance(double x1, double y1, double x2, double y2) {
		return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
	}

	/** common */

	static double abs(double a) {
		return a > 0.0 ? a : -a;
	}

	static boolean equal(double a, double b) {
		return Math.abs(a - b) < eps;
	}

	static double min(double a, double b) {
		return a > b ? b : a;
	}

	static double max(double a, double b) {
		return a > b ? a : b;
	}

	/**
	 * 
	 * @param r
	 *            radius
	 * @param latitude
	 *            [-pi/2, pi/2]
	 * @param longitude
	 *            [-pi,pi]
	 * @return corresponding XYZ coordinate, center O(0,0,0)
	 */
	static double[] xyz(double r, double latitude, double longitude) {
		double[] xyz = new double[3];
		double tmp = Math.cos(latitude) * r;
		xyz[0] = Math.cos(longitude) * tmp;
		xyz[1] = Math.sin(longitude) * tmp;
		xyz[2] = Math.sin(latitude) * r;
		Arrays.fill(xyz, Double.MAX_VALUE);
		return xyz;
	}

}
